题意简述
给定两个字符串，保证比长，在中取出个不重叠的子串，使得顺序拼起来能得到，有多少不同的方案？（相同的子串从不同的位置被取出来也是不同的方案）。
PS：复杂度最高是，因为这个值约等于，所以不能带。
思路
很明显要，因为计数题的方法也没几个，
- DP
- 数据结构优化暴力
- 组合数学
显然，2. 不行（至今没有数据结构能维护这个），3. 不会（太难了，像我会一样），只能考虑一下1。1虽然很难，但是从可做性来讲，只有这个了。
那么如何设状态呢？（千万不要怂，尽管开空间，到时候会优化的）
考虑设表示中前个位置，匹配到的前个位置，用了个子串。那么我们有转移：
珂是我们发现，这样少算了和前面某一个子串合并的情况。
所以我们再加一维，表示没选，表示选了。然后推一下式子：
也就是被扔掉了。所以要凑好个位置，转移：
。选了，首先就是要能和匹配，要不然这个选择是不合法的。此时我们珂以单独出来，或者继承了以前选的某个子串。
单独的方程：
继承的方程：。
然后最后的答案就是。
注意边界。每次枚举了之后都要求一下边界。其中边界条件为：
的匹配数，其中那个匹配数珂以在求下面那个转移的时候顺便统计一下。
若，则
细节问题：由于循环里面也要用，所以代码里面那个被称为
还有一个细节：时间够的，但是空间开不下，要用滚动数组。不过我认为，您能来做这个题，肯定会滚动数组（如果不会赶紧去补！马上了！！！（现改名认证。。。））
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
using namespace std;
namespace Flandre_Scarlet
{
//不要少打一个0（我还真干过。。。）
char a[N],b[M];
int n,m,c;
void R1(int &x)
{
x=0;char c=getchar();int f=1;
while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=(f==1)?x:-x;
}
void Input()
{
R1(n),R1(m),R1(c);
scanf("%s",a+1);
scanf("%s",b+1);
}
int dp[2][M][M][2];
int sum3(int a,int b,int c)
{
return ((a+b)%mod+c)%mod;
}
void Soviet()
{
int cur=0,pre=1;
int s=0;
F(i,1,n)
{
swap(cur,pre);
NOW[1][1][0]=s;//匹配数s
if (a[i]==b[1]) NOW[1][1][1]=1,++s;//s就是顺便统计的匹配数
F(j,2,m) F(k,1,c)
{
if (a[i]==b[j])
{
NOW[j][k][1]=sum3(
PRE[j-1][k-1][1],
PRE[j-1][k][1],
PRE[j-1][k-1][0]
);
}
NOW[j][k][0]=(PRE[j][k][0]+PRE[j][k][1])%mod;
}
FK(PRE);//别忘了清空
}
printf("%d\n",(NOW[m][c][0]+NOW[m][c][1])%mod);
}
void IsMyWife()
{
Input();
Soviet();
}
}
int main()
{
Flandre_Scarlet::IsMyWife();
// while(1);
return 0;
}